package leetcode.interviewClassics;

import java.util.Stack;

/**
 * @author Cheng Jun
 * Description: 栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，
 * 但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek返回 -1。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sort-of-stacks-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * <p>
 * 先考虑 最通用的情况，就是大都数情况，编写的过程中，想到了边界情况，可以想先注释，写完通用情况的编码后，再根据刚才想到的边界情况，一步步完善代码。
 * if 里面最好写 需要最少编码的情况，else 写 复杂的情况。
 * @version 1.0
 * @date 2021/11/5 9:07
 */
public class SortedStack {

    // 排序后的 栈
    private Stack<Integer> elementData;
    // 帮助排序用的临时栈，存放 大于等于 val 的值
    private Stack<Integer> segmentData;
    public SortedStack() {
        elementData = new Stack<>();
        segmentData = new Stack<>();
    }

    public static void main(String[] args) {
        SortedStack sortedStack = new SortedStack();
        sortedStack.push(40);
        sortedStack.push(19);
        sortedStack.push(44);
        sortedStack.push(42);
        sortedStack.push(8);
        sortedStack.push(29);
        sortedStack.push(25);
    }

    public void push(int val) {
        if (elementData.isEmpty()) {
            elementData.push(val);
        } else {
            // 排序，栈顶元素——最小的元素
            Integer peek = elementData.peek();
            // 插入更小的元素
            if (peek >= val) {
                elementData.push(val);
            } else {
                // 大于栈顶元素，要往下移动，一直找到 元素 大于等于 val, 然后插入栈顶
                while (peek < val) {
                    // 注意到栈底
                    segmentData.push(peek);
                    elementData.pop();
                    if (elementData.isEmpty()) {
                        elementData.push(val);
                        break;
                    } else {
                        peek = elementData.peek();
                        if (peek >= val) {
                            elementData.push(val);
                        }
                    }
                }

                // 恢复 elementData
                while (!segmentData.isEmpty()) {
                    elementData.push(segmentData.peek());
                    segmentData.pop();
                }
            }
        }

    }

    public void pop() {
        if (elementData.isEmpty()) {
            return;
        }
        elementData.pop();
    }

    public int peek() {
        if (elementData.isEmpty()) {
            return -1;
        }
        return elementData.peek();
    }

    public boolean isEmpty() {
        return elementData.isEmpty();
    }
}
